package 三个数的最大乘积;

import java.util.Arrays;

/**
 * 三个数的最大乘积，在数组中找出由三个数字组成的最大乘积，并输出这个乘积，不考虑乘积越界
 * 考察：线性扫描
 */
public class Solution {
    public static void main(String[] args) {

        /*
        数组会出现以下三种情况：
        1、全是正数：取3个最大值
        2、全是负数：取3个最大值
        3、有正数，有负数：需要考虑负负得正的情况
            1、只有1个负数，取3个最大值
            2、有2个负数，取2个最小负数 + 1个最大正数

         */
        int[] nums = new int[]{-10, -9, 1, 2, 3, 4, 5};

        int sum = getMaxMin(nums);
        System.out.println("sum = " + sum);
    }

    /**
     * 线性扫描 O(n)
     */
    public static int getMaxMin(int[] nums) {

        // 找出3个最大的，2个最小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

        for (int num : nums) {

            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }

            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }

        }

        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }

    /**
     * 先排序，计算最大值
     */
    public static int binarySearch(int[] nums) {
        // 排过序
        Arrays.sort(nums);
        int n = nums.length;
        // 比较几种情况的值，返回最大
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
    }

}
